package 搜索.BFS;

import java.util.LinkedList;
import java.util.Queue;

/*
解题思路：
    这题一看要求最短路径，第一反应就是BFS。
        这题很简单直接套用BFS模板就行了。
 */
public class 二叉树的最小深度_111 {

    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();//核心数据结构
        if (root == null) {
            return 0;
        }
        queue.add(root);//首先把根节点给加到队列中
        int step = 0;//初始化步数为0

        while (!queue.isEmpty()) {//当队列不空的时候
            step++;//首先步数加一，之所以写在最前面，是因为把root放入队列这也算一步
            int size = queue.size();
            /* 将当前队列中的所有节点向四周扩散 */
            while (size-- > 0) {
                TreeNode tree = queue.poll();
                if (tree.left == null && tree.right == null) {//满足目标直接返回
                    return step;
                }

                if (tree.left != null) {//如果它有节点就把节点放入队列
                    queue.add(tree.left);
                }
                if (tree.right != null) {
                    queue.add(tree.right);
                }
            }
        }
        return -1;
    }
}
